package Offer22;

/**
 * @author 23737
 * @time 2021.9.14
 * 链表中的倒数第k个结点：输入一个链表，输出该链表中倒数第k个节点。
 * 本题从1开始计数，即链表的尾节点是倒数第1个节点。
 */
public class Test {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode kthFromEnd = new Solution().getKthFromEnd(listNode1, 2);
        System.out.println(kthFromEnd.val);
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

/*快慢指针法，原理和暴力解法一样*/
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        while (fast != null) {
            fast = fast.next;
            //当K为0的时候，就是到了节点的值，等循环结束把该节点返回就好了
            if (k == 0) {
                head = head.next;
            } else {
                k--;
            }
        }
        return head;
    }
}

/*暴力遍历法
最简单直接的方法即为顺序查找，假设当前链表的长度为 nn，则我们知道链表的倒数第 kk 个节点即为正数第 n - kn−k 个节点
此时我们只需要顺序遍历到链表的第 n - kn−k 个节点即为倒数第 kk 个节点。
* */
class SolutionTwo {
    public ListNode getKthFromEnd(ListNode head, int k) {
        int n = 0;
        ListNode node = null;
        if (head == null) return null;
        //这里进行链表长度的获取
        for (node = head; node != null; node = node.next) {
            n++;
        }
        //这里进行循环遍历，只运行到第N-K个结点就退出循环，返回结点
        for (node = head; n > k; n--) {
            node = node.next;
        }
        return node;
    }
}

/**
 * 二刷
 */
class SolutionTwice{
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        ListNode fast = head;
        while(fast!=null){
            fast = fast.next;
            if (k == 0) {
                head = head.next;
            }else {
                k--;
            }
        }
        return head;
    }
}